Currently, images, speech, a wide variety of communications signals and numerous other types of information are being represented in the form of digital data.
Unfortunately, due to, e.g., transmission errors, signal interference, etc., digital signals and the sets of digital data represented thereby, often become corrupted by impulse noise. Impulse noise frequently introduces sharp, sudden changes in signal values. For transmitted signals, e.g., audio and/or video signals, this can result in undesired noticeable signal degradation.
In many applications the use of infinite impulse response (IIR) and finite impulse response (FIR) filters can reduce or eliminate some of the undesirable effects of impulse noise. Unfortunately, the use of such filters has undesirable consequences in many applications. for example, the use of FIR and IIR filters on images tends to have the undesirable effect of softening edges within an image and/or blurring images. This is because such filters operate on pixels affected by impulse noise as well as pixel values unaffected by impulse noise.
Median filters have the advantage of modifying a single value at a time, e.g., as a function of adjacent values in a set of digital data values. Median filters replace the value being processed with the median or middle value found in the set of values used to perform the filtering operation. The median value need not be, and in many cases will not be, the average value of the set of values used to perform the filtering operation.
FIG. 1, illustrates a 4.times.4 array of values, e.g., pixel values, where letters A through P each represent a different pixel value, e.g., a value used to represent pixel luminance or chrominance information.
Assume a 3.times.3 median filter were used to filter the pixel value F of FIG. 1. In such a case, the pixel value F would be replaced by the median value in the set of pixel values A, B, C, E, F, G, I, J, K.
Median filters will normally result in the replacement of pixel values which have been affected by impulse noise. However, when applied to images, they also have the undesirable effect of replacing many pixel values which are unaffected by impulse noise as well.
The use of a weighted median filter can reduce the risk that pixel values which are unaffected by impulse noise will be replaced as a result of a median filtering operation. FIG. 2 shows a weighting matrix that can be used to implement a weighted median filter. In a weighted median filter, the weight determines the number of times the corresponding value should be included in the set of values used to determine the median. For example, using the filter weights shown in FIG. 2 to perform a 3.times.3 weighted median filtering operation on the set of pixel values [A, B, C, E, F, G, I, J, K] would result in a set of 21 values, [A, B, B, B, C, E, E, E, F, F, F, F, F, G, G, G, I, J, J, J, K] the median of which would be used to replace the pixel value F which is being filtered.
Because the weighted median filtering operation allows the pixel value being filtered to be weighted more heavily than other values used in the filtering operation, the chance of the pixel value being changed can be controlled so that it is far less than that which occurs in an unweighted median filtering operation. Accordingly, weighted median filters are well suited for filtering impulse noise from images without excessive "softening" of the image that may occur when regular median filters are used.
When weights are used as part of a filtering operation, the weights can be either static, e.g., fixed at the time the filter is initially designed, or dynamic, whereby the filter weights may change with each filtering operation that is performed.
Numerous known techniques exist for dynamically generating filter weights. As will be discussed below, such known techniques may be used with various embodiments of the present invention.
Difficulties in providing enough storage locations to store the relatively large number of values used in a median filtering operation and the difficulty in implementing dedicated hardware capable of determining the median value to be output have lead to most median filtering operations, and weighted median filtering operations in particular, being implemented in software, e.g., using a general purpose computer.
Image processing, and video processing in particular, often involves the processing of large numbers of pixel values in real time, e.g., the time used to display the images being processed. The relatively slow nature of software implemented weighted median filtering operations is a major disadvantage when attempting to perform fast data processing such as real time image processing.
In view of the above, it becomes apparent that there is a need for new and improved methods of implementing weighted median filters and performing weighted median filtering operations. It is desirable that new weighted median filtering methods be relatively fast at processing data. It is also desirable that any hardware implementations be relatively efficient in the way they are implemented. It is also desirable that at least some hardware implementations be capable of supporting dynamic updating of weight values and use of large weight values without the need to provide large numbers of registers.